class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> pointers(primes.size(), 1);
        vector<int> ans(2, 1);
        for(int i = 1; i < n; i++){
            int temp = INT_MAX;
            for(int j = 0; j < pointers.size(); j++){
                temp = min(temp, ans[pointers[j]] * primes[j]);
            }
            ans.push_back(temp);
            for(int j = 0; j < pointers.size(); j++){
                if(ans[pointers[j]] * primes[j] == temp)pointers[j]++;
            }
        }
        return ans[n];
    }
};
/**
 * 2021.8.9
 * DP做法，时间复杂度 O(nm)，空间复杂度 O(nm)。
 * pointers 存着与 primes 数量一致的指针，每个prime 只与 对应指针指向的那个数相乘。
 * 一开始所有指针都指向第一个丑数（1），当这个丑数被某指针使用过后，那个指针就 ++
 * 每轮从所有 [指针指向的数] * [指针对应的 prime] 中选出最小的作为最新丑数，并使所有达成这个条件
 * 的指针 ++ ，总共进行 n 轮。
*/